package com.practice.recursive;

public class FibonacciExpression {
	private int[] f;
	private int[] m;
	
	public void express(int n) {
		f = new int[128];
		f[0] = 1;
		f[1] = 2;
		
		int N = 2;
		while (f[N-1] < n) {
			f[N] = f[N-1] + f[N-2];
			N++;
		}
		
		m = new int[128];
		m[0] = 1;
		for (int i=1; i<N; i++) m[i] = m[i-1] + f[i];
		
		dfs(n, "", N-1);
	}
	
	private void dfs(int n, String solution, int i) {
		if (i < 0) {
			if (n == 0) System.out.println(solution);
			return;
		}
		if (n<0 || n > m[i]) return;
		
		dfs(n - f[i], solution + "1", i-1);
		dfs(n, solution.length()==0? solution : solution + "0", i-1);
	}
	
	public static void main(String[] args) {
		new FibonacciExpression().express(100000000);
	}
}
